/*
 * SimpleGraphImp.java
 *
 * Created on 2007年10月12日, 下午9:18
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
package com.exclamation.util.graph;

import java.util.LinkedList;

/**
 *
 * @author littlerock
 */
public class SimpleGraphImp extends AbstractGraphImp {

    protected int[][] adjMatrix;

    /** Creates a new instance of SimpleGraphImp */
    public SimpleGraphImp() {
        this(false, 10, 10);
    }

    public SimpleGraphImp(boolean directed) {
        this(directed, 10, 10);
    }

    public SimpleGraphImp(boolean directed, int vSize, int eSize) {
        super(directed, vSize, eSize);

        if (vSize > 0) {
            adjMatrix = new int[vSize][vSize];
        } else {
            adjMatrix = new int[10][10];
        }
    }

    protected Vertex creaeVertex(int id) {

        enlargeMatrix(id);

        return new SimpleVertex(id);
    }

    protected Edge createEdge(int id, int from, int to) {
        this.adjMatrix[from - 1][to - 1] = id;
        if (!this.isDirected()) {
            this.adjMatrix[to - 1][from - 1] = id;
        }
        return new SimpleEdge(id, from, to);
    }

    protected void removeEdgeRelation(int e) {
        SimpleEdge edge = (SimpleEdge) getEdge(e);
        this.adjMatrix[edge.tail - 1][edge.head - 1] = 0;
        if (!this.isDirected()) {
            this.adjMatrix[edge.head - 1][edge.tail - 1] = 0;
        }
        edge.tail = 0;
        edge.head = 0;
    }

    protected void removeVertexRelation(int v) {
    }

    private void enlargeMatrix(int id) {
        if (id <= adjMatrix.length) {
            return;
        }
        int[][] newMatrix = new int[id][id];
        for (int i = 0; i < adjMatrix.length; i++) {
            for (int j = 0; j < adjMatrix.length; j++) {
                newMatrix[i][j] = adjMatrix[i][j];
            }
        }
    }

    public Edge addEdge(int from, int to) {
        if (this.getVertex(from) == null || this.getVertex(to) == null) {
            return null;
        }
        if (this.adjMatrix[from - 1][to - 1] != 0) {
            return null;
        }
        return super.addEdge(from, to);

    }

    public Edge addEdge(int id, int from, int to) {
        if (this.getVertex(from) == null || this.getVertex(to) == null) {
            return null;
        }
        if (this.adjMatrix[from - 1][to - 1] != 0) {
            return null;
        }
        return super.addEdge(id, from, to);
    }

    protected GraphImp createNewGraphImp(boolean directed) {
        return new SimpleGraphImp(directed);
    }

    class SimpleVertex extends AbstractVertex {

        SimpleVertex(int id) {
            super(id);
        }

        SimpleVertex(int id, Object value) {
            super(id, value);
        }

        public Edge[] getOutEdges() {
            LinkedList<Edge> edgeList = new LinkedList<Edge>();

            for (int eid : adjMatrix[id - 1]) {
                if (eid != 0) {
                    edgeList.add(getEdge(eid));
                }
            }

            Edge[] reVal = new Edge[edgeList.size()];
            return edgeList.toArray(reVal);
        }

        public Edge[] getInEdges() {
            LinkedList<Edge> edgeList = new LinkedList<Edge>();

            for (int i = 0; i < adjMatrix.length; i++) {
                if (adjMatrix[i][id - 1] != 0) {
                    edgeList.add(getEdge(adjMatrix[i][id - 1]));
                }
            }

            Edge[] reVal = new Edge[edgeList.size()];
            return edgeList.toArray(reVal);
        }

        public Edge[] getEdges() {
            LinkedList<Edge> edgeList = new LinkedList<Edge>();

            if (isDirected()) {
                for (int i = 0; i < adjMatrix.length; i++) {
                    if (adjMatrix[i][id - 1] != 0 && i != id - 1) {
                        edgeList.add(getEdge(adjMatrix[i][id - 1]));
                    }
                }
            }

            for (int eid : adjMatrix[id - 1]) {
                if (eid != 0) {
                    edgeList.add(getEdge(eid));
                }
            }


            Edge[] reVal = new Edge[edgeList.size()];
            return edgeList.toArray(reVal);
        }

        public Graph getGraph() {
            return SimpleGraphImp.this;
        }
    }

    class SimpleEdge extends AbstractEdge {

        int tail;
        int head;

        SimpleEdge(int id, int tail, int head, Object value) {
            super(id, value);
            this.tail = tail;
            this.head = head;
        }

        SimpleEdge(int id, int tail, int head) {
            this(id, tail, head, null);
        }

        public Vertex getTail() {
            return getVertex(tail);
        }

        public Vertex getHead() {
            return getVertex(head);
        }

        public Graph getGraph() {
            return SimpleGraphImp.this;
        }
    }
}
